/*
题目: 子数组的最小值之和
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

https://leetcode.cn/problems/sum-of-subarray-minimums
 */
public class SumSubarrayMin {
    public int sumSubarrayMins(int[] arr) {
        // 单调栈
        int n = arr.length;
        // 求出 对数组中所有的元素为准
        // 这个元素为最小值 的左右边界
        // 或者说, 分别左边界 和 右边界 以这个元素为最小值的 子数组 个数
        // 求出了以这个元素 为 左边界和右边界的子数组个数, 那么以这个元素为最小值的 数组个数就是 left[i] * right[i]
        Stack<Integer> stk = new Stack<> ();
        int[] left = new int[n]; // 以这个元素为左边界并且是最小值的 长度
        int[] right = new int[n];

        // 为了避免重复的子数组运算, 需要一个是 >= 号, 另一个是 > 号
        // 例如 | | | |, 如果两边都有 = 号, 那么就会有重复子数组
        for (int i = 0; i < n; i ++) {
            while (!stk.isEmpty() && arr[stk.peek()] > arr[i]) {
                stk.pop();
            }
            right[i] = i - (stk.isEmpty() ? -1 : stk.peek());
            stk.push(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; i --) {
            while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]) {
                stk.pop();
            }
            left[i] = (stk.isEmpty() ? n : stk.peek()) - i;
            stk.push(i);
        }

        final int MOD = (int) 1e9 + 7;
        int src = 0;
        for (int i = 0; i < n; i ++) {
            src = (int) ((src + (long)left[i] * right[i] * arr[i]) % MOD);
        }
        return src;
    }
}
